home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / KPlib 1.3.5 / KPPriorityQueue.h < prev    next >
Text File  |  1995-12-17  |  7KB  |  268 lines
  1. // A module of KPlib v1.3.5.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_PRIORITY_QUEUE_DEFINED
  6. #define KP_PRIORITY_QUEUE_DEFINED
  7.  
  8. #include <stdlib.h>
  9. #include "KPbasic.h"
  10. #include "KPList.h"
  11.  
  12. // Assumes Element has a default constructor, operator=(), operator==(),
  13. // and operator<().  Note that operator<() must place a total ordering on
  14. // the set of Elements.
  15.  
  16. template <class Element>
  17. class KPPriorityQueue {
  18.     public:
  19.         KPPriorityQueue();
  20.         KPPriorityQueue(const KPPriorityQueue<Element> &queue);
  21.         KPPriorityQueue(const KPList<Element> &list);
  22.         KPPriorityQueue(const Element &element);
  23.         ~KPPriorityQueue();
  24.         operator KPList<Element>() const;
  25.         KPPriorityQueue<Element> &
  26.                             operator=(const KPPriorityQueue<Element> &queue);
  27.         KPPriorityQueue<Element> &operator=(const Element &element);
  28.         KPPriorityQueue<Element> &enqueue(const Element &element);
  29.         Element dequeue();
  30.         Element &head();
  31.         const Element &head() const;
  32.         Element &tail();
  33.         const Element &tail() const;
  34.         bool contains(const Element &element) const;
  35.         int occurrences_of(const Element &element) const;
  36.         int size() const;
  37.         bool is_empty() const;
  38.         KPPriorityQueue<Element> &clear();
  39.     protected:
  40.         static void queue_empty_error(const char *fname);
  41.         KPSortableList<Element> my_list;
  42. };
  43.  
  44. /****************************************************************************/
  45.  
  46. template <class Element>
  47. inline
  48. KPPriorityQueue<Element>::KPPriorityQueue(): my_list()
  49. { /* do nothing. */ }
  50.  
  51. /****************************************************************************/
  52.  
  53. template <class Element>
  54. inline
  55. KPPriorityQueue<Element>::KPPriorityQueue(const KPPriorityQueue<Element>
  56.                                             &queue): my_list(queue.my_list)
  57. { /* do nothing. */ }
  58.  
  59. /****************************************************************************/
  60.  
  61. template <class Element>
  62. inline
  63. KPPriorityQueue<Element>::KPPriorityQueue(const KPList<Element> &list):
  64.                                                                 my_list(list)
  65. {
  66.     my_list.sort();
  67. }
  68.  
  69. /****************************************************************************/
  70.  
  71. template <class Element>
  72. inline
  73. KPPriorityQueue<Element>::KPPriorityQueue(const Element &element):
  74.                                                             my_list(element)
  75. { /* do nothing. */ }
  76.  
  77. /****************************************************************************/
  78.  
  79. template <class Element>
  80. inline
  81. KPPriorityQueue<Element>::~KPPriorityQueue()
  82. {
  83.     my_list.clear();
  84. }
  85.  
  86. /****************************************************************************/
  87.  
  88. template <class Element>
  89. inline
  90. KPPriorityQueue<Element>::operator KPList<Element>() const
  91. {
  92.     return my_list;
  93. }
  94.  
  95. /****************************************************************************/
  96.  
  97. template <class Element>
  98. inline KPPriorityQueue<Element> &
  99. KPPriorityQueue<Element>::operator=(const KPPriorityQueue<Element> &queue)
  100. {
  101.     my_list = queue.my_list;
  102.     return *this;
  103. }
  104.  
  105. /****************************************************************************/
  106.  
  107. template <class Element>
  108. inline KPPriorityQueue<Element> &
  109. KPPriorityQueue<Element>::operator=(const Element &element)
  110. {
  111.     my_list = element;
  112.     return *this;
  113. }
  114.  
  115. /****************************************************************************/
  116.  
  117. template <class Element>
  118. KPPriorityQueue<Element> &
  119. KPPriorityQueue<Element>::enqueue(const Element &element)
  120. {
  121.     KPIterator<Element> iter(my_list);
  122.  
  123.     iter.end();
  124.     while (iter.ptr() && element < *iter)
  125.         iter--;
  126.     if (!iter.ptr())
  127.         my_list.add_to_head(element);
  128.     else
  129.         iter.insert_after_current(element);
  130.  
  131.     return *this;
  132. }
  133.  
  134. /****************************************************************************/
  135.  
  136. template <class Element>
  137. inline Element
  138. KPPriorityQueue<Element>::dequeue()
  139. {
  140.     if (my_list.size() < 1)
  141.         queue_empty_error("dequeue()");
  142.     
  143.     Element element = my_list.head();
  144.     my_list.remove_head();
  145.     return element;
  146. }
  147.  
  148. /****************************************************************************/
  149.  
  150. template <class Element>
  151. inline Element &
  152. KPPriorityQueue<Element>::head()
  153. {
  154.     if (my_list.size() < 1)
  155.         queue_empty_error("head()");
  156.  
  157.     return my_list.head();
  158. }
  159.  
  160. /****************************************************************************/
  161.  
  162. template <class Element>
  163. inline const Element &
  164. KPPriorityQueue<Element>::head() const
  165. {
  166.     if (my_list.size() < 1)
  167.         queue_empty_error("head()");
  168.  
  169.     return my_list.head();
  170. }
  171.  
  172. /****************************************************************************/
  173.  
  174. template <class Element>
  175. inline Element &
  176. KPPriorityQueue<Element>::tail()
  177. {
  178.     if (my_list.size() < 1)
  179.         queue_empty_error("tail()");
  180.  
  181.     return my_list.tail();
  182. }
  183.  
  184. /****************************************************************************/
  185.  
  186. template <class Element>
  187. inline const Element &
  188. KPPriorityQueue<Element>::tail() const
  189. {
  190.     if (my_list.size() < 1)
  191.         queue_empty_error("tail()");
  192.  
  193.     return my_list.tail();
  194. }
  195.  
  196. /****************************************************************************/
  197.  
  198. template <class Element>
  199. bool
  200. KPPriorityQueue<Element>::contains(const Element &element) const
  201. {
  202.     KPReadOnlyIterator<Element> iter(my_list);
  203.  
  204.     while (iter.ptr() && *iter < element)
  205.         iter++;
  206.     return (iter.ptr() && *iter == element);
  207. }
  208.  
  209. /****************************************************************************/
  210.  
  211. template <class Element>
  212. int
  213. KPPriorityQueue<Element>::occurrences_of(const Element &element) const
  214. {
  215.     KPReadOnlyIterator<Element> iter(my_list);
  216.     int n = 0;
  217.  
  218.     while (iter.ptr() && *iter < element)
  219.         iter++;
  220.     while (iter.ptr() && *iter == element) {
  221.         n++;
  222.         iter++;
  223.     }
  224.  
  225.     return n;
  226. }
  227.  
  228. /****************************************************************************/
  229.  
  230. template <class Element>
  231. inline int
  232. KPPriorityQueue<Element>::size() const
  233. {
  234.     return my_list.size();
  235. }
  236.  
  237. /****************************************************************************/
  238.  
  239. template <class Element>
  240. inline bool
  241. KPPriorityQueue<Element>::is_empty() const
  242. {
  243.     return my_list.is_empty();
  244. }
  245.  
  246. /****************************************************************************/
  247.  
  248. template <class Element>
  249. inline KPPriorityQueue<Element> &
  250. KPPriorityQueue<Element>::clear()
  251. {
  252.     my_list.clear();
  253. }
  254.  
  255. /****************************************************************************/
  256.  
  257. template <class Element>
  258. void
  259. KPPriorityQueue<Element>::queue_empty_error(const char *fname)
  260. {
  261.     cerr << "KPPriorityQueue: " << fname << " - queue empty\n";
  262.     exit(EXIT_FAILURE);
  263. }
  264.  
  265. /****************************************************************************/
  266.  
  267. #endif /* KP_PRIORITY_QUEUE_DEFINED */
  268.